package linkedList;

//单链表
public class MyLinkedList {
    //链表结点
    static class Node{
        private String val;
        private Node next = null;

        public Node(String val){
            this.val = val;
        }
    }

    private Node head = null;

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (Node cur = head; cur != null; cur = cur.next){
            stringBuilder.append(cur.val);
            if(cur.next != null){
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    //头插
    public void addFirst(String val){
        //创建新结点
        Node newNode = new Node(val);
        newNode.next = head;
        head = newNode;
    }
    //尾插
    public void addLast(String val){
        //空链表，进行头插
        if(head == null){
            addFirst(val);
            return;
        }
        //创建新结点
        Node newNode = new Node(val);
        //找到链表的尾结点
        Node tail = head;
        for( ; tail.next != null; tail = tail.next){
            ;
        }
        //尾插
        tail.next = newNode;
    }
    //得到单链表的⻓度
    public int size(){
        int size = 0;
        for(Node cur = head; cur != null; cur = cur.next){
            size++;
        }
        return size;
    }
    //按下标插入
    public void add(int index, String val){
        int size = size();
        //检查下标是否合法
        if(index < 0 || index > size){
            throw new IndexOutOfBoundsException("index: " + index +", size: " + size);
        }
        //头插
        if(index == 0){
            addFirst(val);
            return;
        }
        //尾插
        if (index == size){
            addLast(val);
            return;
        }
        Node prev = head;
        //中间插入
        for (int i = 0; i < index - 1; i++){
            prev = prev.next; //找到待插入结点处的前一个结点
        }
        //创建新结点
        Node newNode = new Node(val);
        //新结点指向插入结点
        newNode.next = prev.next;
        prev.next = newNode;
    }
    //头删
    public void removeFirst(){
        if(head == null){
            return;
        }
        head = head.next;
    }
    //尾删
    public void removeLast(){
        //空链表，不用删
        if(head == null){
            return;
        }
        //只有一个结点，删除头结点
        if(head.next == null){
            head = null;
            return;
        }
        Node prev = null;
        Node tail = head;
        //找到尾结点和尾结点的前一个结点
        while(tail != null && tail.next != null){
            prev = tail;
            tail = tail.next;
        }
        //尾结点的前一个结点的next置空
        prev.next = null;
    }
    //按下标index删除结点
    public void remove(int index){
        int size = size();
        //检查下标是否合法
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("index: " + index + ", size: " + size);
        }
        //空链表，不用删
        if(head == null){
            return;
        }
        //头删
        if(index == 0){
            removeFirst();
            return;
        }
        //尾删
        if(index == size - 1){
            removeLast();
            return;
        }
        Node prev = head;
        //删除中间的结点
        for(int i = 0; i < index - 1; i++){
            prev = prev.next;
        }
        prev.next = prev.next.next;
    }
    //删除第⼀次出现关键字为elem的节点
    public boolean remove(String elem){
        //空链表，删除失败
        if(head == null){
            return false;
        }
//        int index = 0;
//        Node cur = head;
//        //找到待删除的元素的下标
//        while(cur != null && cur.val.equals(elem)){
//            cur = cur.next;
//            index++;
//        }
//        //cur等于null，遍历完链表没有找到elem
//        if(cur == null){
//            return false;
//        }
//        //按下标index删除结点
//        remove(index);
//        return true;

        //判断头结点的val是否等于elem，等于则删除头结点
        if(head.val.equals(elem)){
            head = head.next;
            return true;
        }

        Node prev = head;
        Node cur = head.next;
        //删除第一个值等于elem的结点
        while(cur != null){
            //循环遍历，找到待删除的元素，直接删除
            if(cur.val.equals(elem)){
                cur = cur.next;
                prev.next = cur;
                return true;
            }
            //未找到待删除的元素结点，更新prev和cur
            prev = cur;
            cur = cur.next;
        }
        //循环查找结束，未找到要删除的元素结点，返回false
        return false;
    }

    //判断链表是否包含elem
    public boolean contains(String elem){
        if(head == null){
            return false;
        }
        //遍历链表
        for(Node cur = head; cur != null; cur = cur.next){
            //含有elem，返回true
            if(cur.val.equals(elem)){
                return true;
            }
        }
        //链表没有elem，返回false
        return false;
    }
    //删除所有值为elem的节点
    public void removeAll(String elem){
        //空链表，不用删
        if (head == null){
            return;
        }

        Node prev = head;
        Node cur = head.next;
        //删除头结点后面所有值等于elem的结点
        while(cur != null){
            if(cur.val.equals(elem)){
                cur = cur.next;
                prev.next = cur;
                continue;
            }
            prev = cur;
            cur = cur.next;
        }
        //判断头结点的val是否等于elem，等于则删除头结点
        if(head.val.equals(elem)){
            head = head.next;
        }
    }
    //返回下标为index的结点的值
    public String get(int index){
        int size = size();
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("index: " + index + ", size: " + size);
        }
        Node cur = head;
        for(int i = 0; i < index; i++){
            cur = cur.next;
        }
        return cur.val;
    }
    //将下标为index的结点的值设置为elem
    public void set(int index, String elem){
        int size = size();
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException("index: " + index + ", size: " + size);
        }
        Node cur = head;
        for(int i = 0; i < index; i++){
            cur = cur.next;
        }
        cur.val = elem;
    }
    //返回最第一个elem所在的下标
    public int indexOf(String elem){
        int index = 0;
        for (Node cur = head; cur != null; cur = cur.next){
            if(cur.val.equals(elem)){
                return index;
            }
            index++;
        }
        //循环遍历，未找到elem，返回-1
        return -1;
    }
    //返回最后一个elem所在的下标
    public int lastIndexOf(String elem){
        int index = -1;
        int i = 0;
        for (Node cur = head; cur != null; cur = cur.next, i++){
            if(cur.val.equals(elem)){
                index = i;
            }
        }
        return index;
    }
    //判空
    public boolean isEmpty(){
        return head == null;
    }

    //清空链表
    public void clear(){
        head = null;
    }
    //测试头插
    public static void test1(){
        MyLinkedList list = new MyLinkedList();
        list.addFirst("a");
        list.addFirst("b");
        list.addFirst("c");
        list.addFirst("d");
        System.out.println(list);
    }
    //测试尾插
    public static void test2(){
        MyLinkedList list = new MyLinkedList();
        list.addLast("a");
        list.addLast("b");
        list.addLast("c");
        list.addLast("d");
        System.out.println(list);
    }
    //测试按下标插入新结点
    public static void test3(){
        MyLinkedList list = new MyLinkedList();
        list.add(0, "a");
        list.add(1, "b");
        list.add(1, "c");
        list.add(2, "d");
        list.add(2, "e");
        // a c e d b
        System.out.println(list);
    }
    public static void test4(){
        MyLinkedList list = new MyLinkedList();
        list.addLast("a");
        //list.removeFirst();
        list.addLast("b");
        list.addLast("c");
        list.addLast("d");
        //list.removeLast();
        list.remove(2);
        list.remove("b");
        boolean flag = list.remove("b");
        System.out.println(list);
        System.out.println(flag);
        list.remove("a");
        list.remove("d");
        System.out.println(list);
    }
    public static void test5(){
        MyLinkedList list = new MyLinkedList();
        list.addLast("a");
        list.addLast("b");
        list.addLast("a");
        list.addLast("c");
        list.addLast("a");
        System.out.println(list);
        list.removeAll("a");
        System.out.println(list);
        list.add(0, "a");
        list.add(1, "b");
        list.add(1, "c");
        list.add(2, "d");
        list.add(2, "e");
        System.out.println(list);
        System.out.println(list.get(1));
        list.set(4,"wang");
        System.out.println(list);
        System.out.println(list.indexOf("b"));
        System.out.println(list.lastIndexOf("c"));
    }

    public static void main(String[] args) {
        //test1();
        //test2();
        //test3();
        //test4();
        test5();
    }
}
